/**
 * @file openCV 查找轮廓
 * @author mengke01(kekee000@gmail.com)
 */

import smoothContour from './smooth';

const ICV_SINGLE = 1;
const ICV_CONNECTING_ABOVE = 2;
const ICV_CONNECTING_BELOW = 3;

/**
 * 对轮廓横向坐标进行插值
 *
 * @param  {Array} contour 轮廓集合
 * @return {Array}         插值后轮廓集合
 */
function interPolateContour(contour) {
    let newContour = [];
    for (let i = 0, l = contour.length; i < l; i++) {
        let p = contour[i];
        let next = contour[i === l - 1 ? 0 : i + 1];
        newContour.push(p);

        if (Math.abs(p.x - next.x) > 1) {

            let j;
            let n;
            if (p.x < next.x) {
                for (j = p.x + 1, n = next.x; j < n; j++) {
                    newContour.push({
                        x: j,
                        y: p.y
                    });
                }
            }
            else {
                for (j = p.x - 1, n = next.x; j > n; j--) {
                    newContour.push({
                        x: j,
                        y: p.y
                    });
                }
            }
        }
    }


    return newContour;
}

/**
 * 查找轮廓集合
 * @param  {Object} imageData 二值图像数据
 * @param  {number} minimumPoints     最少点数，如果轮廓点个数小于最少点数，则被去除
 * @param  {number} smooth 平滑边界
 * @return {Array}           轮廓集合
 */
export default function cvFindContours(imageData, minimumPoints = 10, smooth = 3) {

    let fg = 0; // 前景色
    let bg = 255; // 背景色

    let data = imageData.data;
    let width = imageData.width;
    let height = imageData.height;

    let extPoints = [];
    let inPoints = [];

    let i;
    let j;
    let k;
    let n;
    let row;

    let connectFlag;
    let upperLine;
    let upperTotal;
    let upperRun;

    let lowerLine;
    let lowerTotal;
    let lowerRun;
    let prevPoint;
    let tmpPrev;

    upperLine = [];
    tmpPrev = {};


    // 填充白框
    for (j = 0; j < height; j++) {
        row = j * width;
        data[row] = bg;
        data[row + width - 1] = bg;
    }

    row = (height - 1) * width;
    for (j = 0; j < width; j++) {
        data[j] = bg;
        data[row + j] = bg;
    }

    // 查找 第一行
    for (j = 0; j < width;) {
        for (; j < width && data[j] === bg; j++) {
        }

        if (j === width) {
            break;
        }

        tmpPrev.next = {
            x: j,
            y: 0
        };

        upperLine.push(tmpPrev = tmpPrev.next);

        for (; j < width && data[j] === fg; j++) {
        }

        tmpPrev.next = tmpPrev.link = {
            x: j - 1,
            y: 0
        };
        upperLine.push(tmpPrev = tmpPrev.next);
    }

    // 查找中间行
    for (i = 1; i < height; i++) {

        row = i * width;
        lowerLine = [];

        for (j = 0; j < width;) {
            for (; j < width && data[row + j] === bg; j++) {
            }

            if (j === width) {
                break;
            }

            tmpPrev.next = {
                x: j,
                y: i
            };

            lowerLine.push(tmpPrev = tmpPrev.next);

            for (;j < width && data[row + j] === fg; j++) {
            }

            tmpPrev.next = tmpPrev.link = {
                x: j - 1,
                y: i
            };
            lowerLine.push(tmpPrev = tmpPrev.next);
        }

        upperTotal = Math.floor(upperLine.length / 2);
        lowerTotal = Math.floor(lowerLine.length / 2);
        upperRun = upperLine[0];
        lowerRun = lowerLine[0];

        connectFlag = ICV_SINGLE;

        // 查找当前行和上一行之间的连接
        for (k = 0, n = 0; k < upperTotal && n < lowerTotal;) {

            switch (connectFlag) {
                case ICV_SINGLE:
                    if (upperRun.next.x < lowerRun.next.x) {
                        if (upperRun.next.x >= lowerRun.x - 1) {
                            lowerRun.link = upperRun;
                            connectFlag = ICV_CONNECTING_ABOVE;
                            prevPoint = upperRun.next;
                        }
                        else {
                            upperRun.next.link = upperRun;
                        }

                        k++;
                        upperRun = upperRun.next.next;
                    }
                    else {
                        if (upperRun.x <= lowerRun.next.x + 1) {
                            lowerRun.link = upperRun;
                            connectFlag = ICV_CONNECTING_BELOW;
                            prevPoint = lowerRun.next;
                        }
                        else {
                            lowerRun.link = lowerRun.next;
                            extPoints.push(lowerRun);
                        }
                        n++;
                        lowerRun = lowerRun.next.next;
                    }
                    break;

                case ICV_CONNECTING_ABOVE:
                    if (upperRun.x > lowerRun.next.x + 1) {
                        prevPoint.link = lowerRun.next;
                        connectFlag = ICV_SINGLE;
                        n++;
                        lowerRun = lowerRun.next.next;
                    }
                    else {
                        prevPoint.link = upperRun;
                        if (upperRun.next.x < lowerRun.next.x) {
                            k++;
                            prevPoint = upperRun.next;
                            upperRun = upperRun.next.next;
                        }
                        else {
                            connectFlag = ICV_CONNECTING_BELOW;
                            prevPoint = lowerRun.next;
                            n++;
                            lowerRun = lowerRun.next.next;
                        }
                    }
                    break;

                case ICV_CONNECTING_BELOW:
                    if (lowerRun.x > upperRun.next.x + 1) {
                        upperRun.next.link = prevPoint;
                        connectFlag = ICV_SINGLE;
                        k++;
                        upperRun = upperRun.next.next;
                    }
                    else {
                        // First point of contour
                        inPoints.push(lowerRun);
                        lowerRun.link = prevPoint;

                        if (lowerRun.next.x < upperRun.next.x) {
                            n++;
                            prevPoint = lowerRun.next;
                            lowerRun = lowerRun.next.next;
                        }
                        else {
                            connectFlag = ICV_CONNECTING_ABOVE;
                            k++;
                            prevPoint = upperRun.next;
                            upperRun = upperRun.next.next;
                        }
                    }
                    break;
            }
        }

        for (; n < lowerTotal; n++) {

            if (connectFlag !== ICV_SINGLE) {
                prevPoint.link = lowerRun.next;
                connectFlag = ICV_SINGLE;
                lowerRun = lowerRun.next.next;
                continue;
            }

            lowerRun.link = lowerRun.next;

            // First point of contour
            extPoints.push(lowerRun);
            lowerRun = lowerRun.next.next;
        }

        for (; k < upperTotal; k++) {

            if (connectFlag !== ICV_SINGLE) {
                upperRun.next.link = prevPoint;
                connectFlag = ICV_SINGLE;
                upperRun = upperRun.next.next;
                continue;
            }

            upperRun.next.link = upperRun;
            upperRun = upperRun.next.next;
        }

        upperLine = lowerLine;
    }

    upperTotal = Math.floor(upperLine.length / 2);
    upperRun = upperLine[0];

    // the last line of image
    for (k = 0; k < upperTotal; k++) {
        upperRun.next.link = upperRun;
        upperRun = upperRun.next.next;
    }

    let contours = [];
    let count = 0;
    let curPoint;
    let startPoint;
    let contour;
    let points;

    // 查找轮廓集合
    for (k = 0; k < 2; k++) {

        points = k === 0 ? extPoints : inPoints;
        for (j = 0, n = points.length; j < n; j++, count++) {

            startPoint = curPoint = points[j];

            if (!curPoint.link) {
                continue;
            }

            contour = [];

            do {
                contour.push({
                    x: curPoint.x,
                    y: curPoint.y
                });

                let temp = curPoint;
                curPoint = curPoint.link;
                temp.link = 0;

            } while (curPoint && curPoint !== startPoint);

            if (contour.length < 4) {
                continue;
            }

            contour = interPolateContour(contour);

            if (contour.length >= minimumPoints) {
                if (smooth > 1 && contour.length >= 2 * smooth) {
                    contour = smoothContour(contour, smooth);
                }
                contour.flag = k === 0 ? 0 : 1;
                contours.push(contour);
            }
        }
    }

    return contours;
}
